//
// Created by hay boy on 2022/7/19.
//

#ifndef ALGORITHMS_UNITEUSETREE2_H
#define ALGORITHMS_UNITEUSETREE2_H
struct unionFindNode{
    int parent;
    bool root;
    unionFindNode(){
        parent = 1;
        root = true;
    }
};
unionFindNode* node2;
void initialize2(int numberOfElements){
    node2 = new unionFindNode[numberOfElements+1];
}
int find2(int theElement){
    while(!node2[theElement].root){
        theElement = node2[theElement].parent;
    }
    return theElement;
}
int find3(int theElement){
    int theRoot = theElement;
    while(!node2[theRoot].root){
        theRoot = node2[theRoot].parent;
    }
    int currentNode = theElement;
    while(currentNode!=theRoot){
        int parentNode = node2[currentNode].parent;
        node2[currentNode].parent = theRoot;
        currentNode = parentNode;
    }
    return theRoot;
}
void unite2(int rootA,int rootB){
    if(node2[rootA].parent<node2[rootB].parent){
        node2[rootB].parent += node2[rootA].parent;
        node2[rootA].root = false;
        node2[rootA].parent = rootB;
    }else{
        node2[rootA].parent += node2[rootB].parent;
        node2[rootB].root = false;
        node2[rootB].parent = rootA;
    }
}
#endif //ALGORITHMS_UNITEUSETREE2_H
